// 给定一个整数数组 nums ，
// 找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

const maxSubArray = function (nums: number[]): number {
    if (nums.length < 1) return 0; // 安全检测
    let res: number = nums[0]; // 结果变量
    let preDp: number = nums[0];
    for (let i = 1; i < nums.length; i++) {
        preDp = Math.max(preDp + nums[i], nums[i]);
        res = Math.max(res, preDp);
    }
    return res;
};


// 这道题目也是一道比较典型的动态规划求解问题
// 首先我们思考动态规划定义的状态
// 我们用一个变量dp，dp表示包含当前元素的最大连续子数组和
// 首先我们扫描这个数组，每当一个新元素出现的时候，我们存在下列决策：
// 1. 将这个新元素加入当前的dp值
// 2. 我们需要判断这个新的dp值和当前元素哪个大（因为旧的dp值可正可负）
// 3. 将大的值存入dp（因为加和后可能变小，变小的话说明不如直接单这个元素作为开头）
// 此时，我们还需要另一个元素res来记录过程中曾经出现过的最大值
// 因为dp算着算着可能变小，最后返回这个res即可得到最大和。